package algorithm.middle;

import jdk.nashorn.internal.objects.NativeUint8Array;

import java.util.Arrays;

public class WiggleSort324 {

    /**
     * 给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
     * <p>
     * 你可以假设所有输入数组都可以得到满足题目要求的结果。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [1,5,1,1,6,4]
     * 输出：[1,6,1,5,1,4]
     * 解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/wiggle-sort-ii
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param nums
     */

    public void wiggleSort(int[] nums) {
        int[] copy = Arrays.copyOf(nums, nums.length);
        //  1 1 2 2 2 3
        Arrays.sort(copy);
        // 112 -> 211
        // 223 -> 322
        // 2 3 1 2 1 2 x
        int len = nums.length;
        int halfLen = len / 2;
        for (int i = 0; i <= halfLen; i++) {
            if (i*2<len){
                nums[i * 2] = copy[len - 1 - i - halfLen];
            }
            if (i * 2 + 1 < len) {
                nums[i * 2 + 1] = copy[len - 1 - i];
            }
        }
    }

    public static void main(String[] args) {
        new WiggleSort324().wiggleSort(new int[]{1, 4, 3, 4, 1, 2, 1, 3, 1, 3, 2, 3, 3});
    }
}
